package Top200;

/**
 * @author zhangmin
 * @create 2022-02-27 15:47
 * dp[i][j]表示s1[0..i-1]和s2[0..j-1]是否可以交错而成s3[i+j-1]
 */
public class isInterleave97 {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n1=s1.length(),n2=s2.length(),n3=s3.length();
        if (n1+n2!=n3) return false;
        boolean[][] dp=new boolean[n1+1][n2+1];
        dp[0][0]=true;
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                if (i>0){
                    dp[i][j]=dp[i][j]||(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1));
                }
                if (j>0){
                    dp[i][j]=dp[i][j]||(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1));
                }
            }
        }
        return dp[n1][n2];
    }
}
